#include "stdio.h"
#include "unistd.h"
#include "stdlib.h"
#include "sys/types.h"
#include "sys/stat.h"
#include "fcntl.h"
#include "pwd.h"
#include "grp.h"
#include "dirent.h"
#define NAME_SIZE 100
typedef struct item
{
	char name[NAME_SIZE];
	int length;
	struct stat st;
	struct item *next;
}nNode;

#define MARK_FILE(value,flags) ((flags) = (((value)&ALL_FILE)|(flags)))
#define DEL_FILE(value,flags)  ((flags) = ((~(value))&(flags)))
#define MARK_INFO(value,flags) ((flags) = (((value)&STAT_ALL_INFO)|(flags)))
#define DEL_INFO(value,flags)  ((flags) = ((~(value))&(flags)))
#define MARK(value,flags)      ((flags) = ((value)|(flags)))
#define DEL(value,flags)       ((flags) = ((~(value))&(flags)))

#define FILE_TYPE  0xf8000000
#define OTH_FILE   0x80000000
#define DIR_FILE   0x40000000
#define REG_FILE   0x20000000
#define BAK_FILE   0x10000000
#define DOT_FILE   0x08000000
#define ALL_FILE   0xf8000000

#define STAT_ALL_INFO   0x07f00000
#define STAT_GROUP      0x04000000
#define STAT_OWNER      0x02000000
#define STAT_NUMID      0x01000000
#define STAT_SIZE       0x00800000   //0 present bytes 1 present k or m 
#define STAT_INODE      0x00400000
#define STAT_TIME       0x00200000
#define STAT_PERMISSION 0x00100000

#define STAT_COLOR      0x00080000      
#define STAT_RECUR      0x00040000
#define STAT_HR         0x00020000
void AddnNode(nNode **head,char *name,struct stat *st);
void freeNode(nNode *head );
void do_ls(char *filename,int flags,nNode **head);
void showitem(char *name ,struct stat *st,int flags);
void showfile(nNode *head,int flags);
void quitsort(char **array,int high,int low);




void format_permission(struct stat *st)
{
	int mode = st->st_mode;
	char buf[12];
	memset(buf,'-',11);
	buf[11]=0;

	if(S_ISDIR(mode))  buf[0] = 'd';
	else if(S_ISCHR(mode))  buf[0] = 'c';
	else if(S_ISBLK(mode))  buf[0] = 'b'; 
	else if(S_ISFIFO(mode)) buf[0] = 'p';
	else if(S_ISLNK(mode))  buf[0] = 'l';
	else if(S_ISSOCK(mode)) buf[0] = 's';
	     
    if(S_IRUSR&mode) buf[1] = 'r';
    if(S_IWUSR&mode) buf[2] = 'w';
    if(S_IXUSR&mode) buf[3] = 'x';

    if(S_IRGRP&mode) buf[4] = 'r';
    if(S_IWGRP&mode) buf[5] = 'w';
    if(S_IXGRP&mode) buf[6] = 'x';

    if(S_IROTH&mode) buf[7] = 'r';
    if(S_IWOTH&mode) buf[8] = 'w';
	if(S_IXOTH&mode) buf[9] = 'x';
	
	if(S_ISUID&mode) buf[3] = 's';
	if(S_ISGID&mode) buf[6] = 's';
	if(S_ISVTX&mode) buf[10] = 's';
	printf("%s  ",buf);
}

void format_group(struct stat *st)
{
	int id = st->st_uid;
	struct group *buf = getgrgid(id);
	if(buf)
	{
		printf("%s  ",buf->gr_name);
	}else
	{
		printf("%d  ",id);
	}
}

void format_owner(struct stat *st)
{
	int id = st->st_gid;
	struct passwd *buf_pw = getpwuid(id);
	if(buf_pw)
	{
		printf("%s ",buf_pw->pw_name);
	}else
	{
		printf("%d ",id);
	}
}

void format_time(struct stat *st)
{
	char *buf= ctime(&(st->st_ctime));
	buf +=4;
	buf[strlen(buf)-1]=0;
	printf("%s  ",buf);
}

void format_numid(struct stat *st)
{
	printf("%d %d  ",st->st_uid,st->st_gid);
}


void main(int argc,char **argv)
{
	int flags =REG_FILE|DIR_FILE|BAK_FILE|OTH_FILE;
	int *file_index = (int *)malloc(sizeof(int)*argc);
	int files= 0;
	int i=0;
	for(i=1;i<argc;i++)
	{
		if(!strcmp(argv[i],"-a"))
		{
			MARK_FILE(ALL_FILE,flags);
			MARK_INFO(STAT_ALL_INFO,flags);
			DEL_INFO(STAT_NUMID,flags);
		}else if(!strcmp("-A",argv[i]))
		{
			DEL_FILE(DOT_FILE,flags);
		}else if(!strcmp("-d",argv[i]))
		{
			MARK_FILE(DIR_FILE,flags);
		}else if(!strcmp("-D",argv[i]))
		{
			DEL_FILE(DIR_FILE,flags);
		}else if(!strcmp("-r",argv[i]))
		{
			MARK_FILE(REG_FILE,flags);
		}else if(!strcmp("-R",argv[i]))
		{
			DEL_FILE(REG_FILE,flags);
		}else if(!strcmp("-o",argv[i]))
		{
			MARK_FILE(OTH_FILE,flags);
		}else if(!strcmp("-O",argv[i]))
		{
			DEL_FILE(OTH_FILE,flags);
		}else if(!strcmp("-B",argv[i]))
		{
			DEL_FILE(BAK_FILE,flags);
		}else if(!strcmp("-l",argv[i]))
		{
			MARK_FILE(ALL_FILE,flags);
			MARK_INFO(STAT_ALL_INFO,flags);
			DEL(STAT_HR,flags);
			DEL(STAT_NUMID,flags);
		}else if(!strcmp("-g",argv[i]))
		{
			MARK_INFO(STAT_GROUP,flags);
			DEL_INFO(STAT_GROUP,flags);
		}else if(!strcmp("-G",argv[i]))
		{
			DEL_INFO(STAT_GROUP,flags);
		}else if(!strcmp("-u",argv[i]))
		{
			MARK_INFO(STAT_OWNER,flags);
			DEL_INFO(STAT_NUMID,flags);
		}else if(!strcmp("-U",argv[i]))
		{
			DEL_INFO(STAT_OWNER,flags);
		}else if(!strcmp("-n",argv[i]))
		{
			MARK_INFO(STAT_NUMID,flags);
			DEL_INFO(STAT_OWNER,flags);
			DEL_INFO(STAT_GROUP,flags);
		}else if(!strcmp("-i",argv[i]))
		{
			MARK_INFO(STAT_INODE,flags);
		}else if(!strcmp("-I",argv[i]))
		{
			DEL_INFO(STAT_INODE,flags);
		}else if(!strcmp("-t",argv[i]))
		{
			MARK_INFO(STAT_TIME,flags);
		}else if(!strcmp("-T",argv[i]))
		{
			DEL_INFO(STAT_TIME,flags);
		}else if(!strcmp("-c",argv[i]))
		{
			MARK(STAT_COLOR,flags);
		}else if(!strcmp("-rec",argv[i]))
		{
			MARK(STAT_RECUR,flags);
		}else if(!strcmp("-h",argv[i]))
		{
			MARK(STAT_HR,flags);
			DEL_INFO(STAT_SIZE,flags);
		}
		else 
		{
			file_index[files++] = i;
		}
	}
	
	if(files==0)
	{
		char path[1024];
		nNode *head=NULL;
		if(-1==getcwd(path,1024))
			return;
		printf("%s : \n",path);
		do_ls(path,flags,&head);
		showfile(head,flags);
	}
	else
	{
		for(i=0;i<files;i++)
		{
			nNode *head=NULL;
			char path[1024];
			do_ls(argv[file_index[i]],flags,&head);
			if(-1 == getcwd(path,1024))
				return;
			printf("%s : \n",path);
			showfile(head,flags);
			freeNode(head);
			printf("\n");
		}
	}
}

int ListLength(nNode *head)
{
	int length=0;
	while(head)
	{
		length++;
		head = head->next;
	}
	return length;
}

void display(nNode *array[],int length,int flags)
{
	int i=0;
	if(flags & STAT_ALL_INFO)
	{
		for(i=0; i < length;i++)
		{
			showitem(array[i]->name,&(array[i]->st),flags);
		}
		printf("\n\n");
	}
	else
	{
		int columns = 97;
		int maxcolumns = 10; 
		int columnpos[10]={0},col=10,j;
		
		for(i = maxcolumns ;i >=1;i -=1 )
		{
			col = i;
			for(j = 0;(j < i) && (j < length);j++)
			{
				int max=0,k=j;
				while(k < length)
				{
					if(array[k]->length > array[max]->length)
						max = k;
					k = k + i;
				}
				columnpos[j] = array[max]->length +3;
			}
			int z;
			for(z=1;z < j; ++z )
			{
				columnpos[z] +=columnpos[z-1];
			}
			if(columnpos[z-1] <= columns)
				break;
		}
		char line[97];
		for(i=0;i < length;i++)
		{
			if( (i % col) == 0 )
			{
				if(i!=0)
				{
					printf("%s",line);
					printf("\n");
				}
				memset(line,' ',96);
				line[96]=0;
				strncpy(line,array[i]->name,strlen(array[i]->name));
			}
			else
			{
				int pos = columnpos[ (i%col)-1 ];
				strncpy(line+pos,array[i]->name,strlen(array[i]->name));
			}
		}
		printf("%s\n",line);
	}
}

void showfile(nNode *head,int flags)
{
	int length = ListLength(head);
	int i=0;
	unsigned int *array = (unsigned int *)malloc(sizeof(unsigned int )*length);
	if(!array)
	{
		perror("array memory error");
		return ;
	}
	for(i=0;i<length;i++)
	{
		array[i] = (unsigned int)head;
		head = head->next;
	}
	quitsort(array,length -1 , 0 );
	display(array,length,flags);
}

void showitem(char *name ,struct stat *st,int flags)
{
	if( (name[strlen(name)-1]=='~') && (!(BAK_FILE&flags)))
		return ;
	if( (name[0]=='.') && (!(DOT_FILE&flags)))
		return;
		
	if( S_ISDIR(st->st_mode) && (!(DIR_FILE&flags)))
		return;
	if( S_ISREG(st->st_mode) && (!(REG_FILE&flags)))
		return;
	
	if(flags & STAT_ALL_INFO)
	{
		format_permission(st);
		printf("%d  ",st->st_nlink);
	}
	if(flags & STAT_OWNER)
		format_owner(st);
	if(flags & STAT_GROUP)
		format_group(st);
	if(flags & STAT_NUMID)
		format_numid(st);
		
	if(flags & STAT_SIZE)
		printf("%d  ",st->st_size);
	else if(flags & STAT_HR)
		printf("%-dk  ",st->st_size/1024 +1);
	
	if(flags &STAT_INODE)
		printf("%d  ",st->st_ino);
	if(flags &STAT_TIME)
		format_time(st);
	printf("%s   ",name);
	if(flags & (STAT_ALL_INFO))
		printf("\n");
}

void AddnNode(nNode **head,char *name,struct stat *st)
{
	nNode *p = (nNode *)malloc(sizeof(nNode));
	if(!p)
		perror("malloc memory error");
	p->next = *head;
	*head = p;
	(*head) -> length = strlen(name);
	strcpy((*head)->name,name);
	memcpy(&((*head)->st),st,sizeof(struct stat));
}

void freeNode(nNode *head )
{
	nNode *p=head;
	while(p)
	{
		p = head->next;
		free(head);
		head = p;
	}
}

void swap(char **array,int i,int j)
{
	char *tmp = array[i];
	array[i] = array[j];
	array[j] = tmp;
}

void quitsort(char **array,int high,int low)
{
	int l=low,h=high;
	char *tmp = array[low];
	while(l < h)
	{
		while(l < h)
		{
			if( strcmp(array[l], tmp ) > 0 )
			{
				swap(array,l,h);
				--h;
				break;
			}
			++l;
		}
		while(l < h)
		{
			if(strcmp(array[h],  tmp) < 0 )
			{
				swap(array,l,h);
				++l;
				break;
			}
			--h;
		}
	}
	if(strcmp(array[l], tmp) > 0 )
	{
		--l;
	}
	if(low < high)
		swap(array,l,low);
	if(low < l)
		quitsort(array,l-1,low);
	if(l < high)
		quitsort(array,high,l+1);
}


void do_ls(char *filename,int flags,nNode **head)
{
	DIR *dir;
	char parent_dir[100];
	struct dirent *direntp;
	struct stat st;
	
	if((dir = opendir(filename))==NULL)
	{
		perror("open dir error");
		goto OPENDIR_ERROR;
	}
	if(-1 == getcwd(parent_dir,100))
	{	
		perror("get parent dir error");
		goto GETCURDIR_ERROR;
	}
	if(-1 == chdir(filename))
	{
		perror("change dir error");
		goto CHDIR_ERROR;
	}
	
	while( (direntp = readdir(dir)) != NULL)
	{
		if(-1 == stat(direntp->d_name,&st))
			continue;
		if((!(flags & STAT_ALL_INFO)) && (direntp->d_name[0] == '.') )
			continue;
		AddnNode(head,direntp->d_name,&st);
		if(S_ISDIR(st.st_mode) && (flags&STAT_RECUR) && strcmp(".",direntp->d_name)&&strcmp( direntp->d_name,".."))
		{
			nNode *newhead=NULL;
			do_ls(direntp->d_name,flags,&newhead);
			printf("%s :\n",direntp->d_name);
			showfile(newhead,flags);
			freeNode(newhead);
		}
	}
	
	if(-1 == chdir(parent_dir))
	{
		perror("go back to parent error");
		goto CHDIR_ERROR;
	}

CHDIR_ERROR:
GETCURDIR_ERROR:
	closedir(dir);
OPENDIR_ERROR:
	;
}